
\chapter{Structures}


A structure corresponds to what is called a record in some other
languages: a data structure with a fixed set of named fields or slots,
known in {\bf T} as {\it components\/}.  For example, one might want an
``employee'' structure, with slots for the employee's name, age, and
salary.  A structure, then, is an organized set of {\it locations\/}, places
to store things.
\index{structures}


\section{Terminology}


Every structure has an associated an object called a \iix{structure
type} (sometimes abbreviated \iix{stype}, pronounced ``ess type'').
Structure types are created by the procedure {\tt MAKE-STYPE} (see below)
and by the special form {\tt DEFINE-STRUCTURE-TYPE}

Given a structure type {\it S\/}, one can access several things of interest:
\begin{description}
\item[{Constructor}]
a procedure that will create uninitialized structures of
type {\it S\/} (e.g., the structure for a particular employee).

\item[{Predicator}]
a procedure (a type predicate) that returns true if its
  argument is a structure of type {\it S\/}.

\item[{Component selectors}]
procedures that access the various components of
  structures of type {\it S\/} (one selector per component).

\item[{Handler}]
the mechanism for specifying how a set of generic operations
will behave when applied to structures of type {\it S\/}.
\end{description}


\section{Defining structure types}


The {\tt DEFINE-STRUCTURE-TYPE} macro is a convenient way to define a new structure type and its
associated constructor, predicator, and component selectors.
{\tt DEFINE-STRUCTURE-TYPE} is a macro defined in terms of {\tt MAKE-STYPE} and
the other low-level routines described in the next section.  One may
want to define one's own interface to these routines, one that
initializes the components when a new instance is constructed, for
example.

\index{DEFINE-STRUCTURE-TYPE@{\tt DEFINE-STRUCTURE-TYPE}}
{\mbox {\tt (DEFINE-STRUCTURE-TYPE {\it typename \{components\}$^+$ \{methods\}$^*$\ \/}) $\longrightarrow$\  {\it stype\/}}}
\hfill Special form

\begin{inset}{}
Creates a structure type (using {\tt MAKE-STYPE}),
and defines a number of variables:
\begin{itemize}
\item[{}]{\it typename\/}{\tt -STYPE} is defined to be the structure type.

\item[{}]{\tt MAKE-}{\it typename\/} is defined to be the constructor.

\item[{}]{\it typename\/}{\tt ?} is defined to be the predicator.

\item[{}]{\it typename\/}{\tt -}{\it componentname\/} is defined to be a component selector, for
each of the {\it componentnames\/}.
\end{itemize}
For example,
\begin{codexenv}
(DEFINE-STRUCTURE-TYPE EMPLOYEE NAME AGE SALARY)
\end{codexenv}
defines
\begin{itemize}
\item[{}]{\tt EMPLOYEE-STYPE}, a variable whose value is
the structure type whose name is {\tt EMPLOYEE}.

\item[{}]{\tt (MAKE-EMPLOYEE)}, a procedure that creates uninitialized
{\tt EMPLOYEE}-structures.

\item[{}]{\tt (EMPLOYEE? {\it object\/})}, a type predicate.

\item[{}]
\begin{codexenv}
{\tt (EMPLOYEE-NAME {\it employee\/}) \\
(EMPLOYEE-AGE {\it employee\/}) \\
(EMPLOYEE-SALARY {\it employee\/})}
\end{codexenv}
selectors that access the components of {\tt EMPLOYEE}-structures.

\end{itemize}

{\it methods} is an optional list of method clauses.  For example,

{\tt \begin{tabbing}
(DEFINE-STRUCTURE-TYPE \= EMPLOYEE \+  \\
	NAME \\
	AGE \\
	SALARY \\
	(((HUMAN? SELF) '\#{\tt T}) \\
	(\= PRINT SELF PORT) \+ \\
	 (FORMAT \= PORT "\#\{Employee ($\tilde{}$A) $\tilde{}$A \}" \+ \\
		 (OBJECT-HASH SELF) \\
		 (EMPLOYEE-NAME SELF)))))
\end{tabbing}}

The methods in the methods clauses cannot reference the components
directly.  They must use the standard structure accessors.  For
example, in the print method above the {\it name} component of the 
{\it employee} structure must be
accessed as {\tt (EMPLOYEE-NAME SELF)} {\bf not} as {\tt NAME}.

\end{inset} 

\section{Manipulating structure types}


\index{MAKE-STYPE@{\tt MAKE-STYPE}}
{\mbox {\tt (MAKE-STYPE {\it typename componentnames method-handler\/}) $\longrightarrow$\  {\it stype\/}}}
\hfill  

\begin{inset}{}
Returns a new structure type.  The {\it typename\/}, which should be a
symbol, is used for printing and identification purposes only.
{\it Componentnames\/} should be a list of symbols.  The {\it componentnames\/}
correspond to the components that instances of the structure will have.
The {\it method-handler\/} should be an object that handles whatever
operations are required, or '\#{\tt F}, if a handler is not required.

For example:
\begin{codexenv}
(MAKE-STYPE 'EMPLOYEE '(NAME AGE SALARY) '\#{\tt F})  $\Longrightarrow$\   \#\{Stype EMPLOYEE\}
\end{codexenv}
This creates a structure type, identified as {\tt EMPLOYEE},
whose instances have components {\tt NAME}, {\tt AGE}, and {\tt SALARY}.
The object returned, a structure type, is appropriate as an argument to other
routines described in this section. However,
{\tt \begin{tabbing}
(MAKE-STYPE \= 'EMPLOYEE \+  \\
	    '(NAME AGE SALARY) \\
	    (OBJECT \= NIL \+  \\
		    ((EMP? SELF) '\#{\tt T}))) \-  \\
    $\Longrightarrow$\  \#\{Stype EMPLOYEE\}
\end{tabbing}}
defines an {\it stype\/} that handles the predicate {\mbox {\tt EMP?}}.
\end{inset}

\index{STYPE-ID@{\tt STYPE-ID}}
{\mbox {\tt (STYPE-ID {\it stype\/}) $\longrightarrow$\  {\it typename\/}}}
\hfill  

\begin{inset}{}
Returns the type identifier for {\it stype\/}.
\end{inset} 

\index{STYPE-CONSTRUCTOR@{\tt STYPE-CONSTRUCTOR}}
{\mbox {\tt (STYPE-CONSTRUCTOR {\it stype\/}) $\longrightarrow$\  {\it procedure\/}}}
\hfill  

\begin{inset}{}
Given a structure type {\it stype\/}, returns the procedure which will
instantiate (i.e., create instances of) the structure type.  The
constructor procedure takes no arguments and creates a structure with
uninitialized components.

Note that the constructor procedure is created at the time the structure type
is created, not at the time that {\tt STYPE-CONSTRUCTOR} is called.
\begin{codexenv}
((STYPE-CONSTRUCTOR {\it stype\/}))  $\equiv$  (COPY-STRUCTURE (STYPE-MASTER {\it stype\/}))
\end{codexenv}
\end{inset} 

\index{STYPE-MASTER@{\tt STYPE-MASTER}}
{\mbox {\tt (STYPE-MASTER {\it stype\/}) $\longrightarrow$\  {\it structure\/}}}
\hfill  

\begin{inset}{}
Returns the ``master copy'' from which all structures created by the
structure type's constructor-procedure are made.
This can be convenient for establishing default values for components in
newly created structures.  The way to do this is by storing into the
master copy the desired default values; these values will be copied
into all new instances of the structure type.  For example,
\begin{codexenv}
(SET (EMPLOYEE-SALARY (STYPE-MASTER EMPLOYEE-STYPE)) 12000) \\
(EMPLOYEE-SALARY (MAKE-EMPLOYEE))  $\Longrightarrow$\   12000
\end{codexenv}
\end{inset} 

\index{STYPE-PREDICATOR@{\tt STYPE-PREDICATOR}}
{\mbox {\tt (STYPE-PREDICATOR {\it stype\/}) $\longrightarrow$\  {\it procedure\/}}}
\hfill  

\begin{inset}{}
Given a structure type {\it stype\/}, returns the procedure (a type predicate)
which will predicate
membership in the structure type.  This procedure takes one
argument and returns true if that argument is an instance of the structure type.

Note that the predicator procedure is created at the time the structure type
is created, not at the time that {\tt STYPE-PREDICATOR} is called.
\end{inset} 

\index{STYPE-SELECTOR@{\tt STYPE-SELECTOR}}
{\mbox {\tt (STYPE-SELECTOR {\it stype componentname\/}) $\longrightarrow$\  {\it procedure\/}}}
\hfill  

\begin{inset}{}
Given a structure type {\it stype\/}, returns the procedure which will
select the component of the structure type's instances identified by
{\it componentname\/}.  The selector procedure takes one argument, which
must be a structure whose structure type is {\it stype\/}, and returns the
appropriate component of the instance.

Such selector procedures support {\tt SETTER} operations, which is to say
that one may alter components of structures by using {\tt SET} or related
special forms.

The effect of selecting a structure component that has not been
previously set, or initialized from the master structure
(see {\tt STYPE-MASTER}, above), is undefined.

Note that the selector procedures are created at the time the structure type
is created, not at the time that {\tt STYPE-SELECTOR} is invoked.
\end{inset} 

\index{STYPE-SELECTORS@{\tt STYPE-SELECTORS}}
{\mbox {\tt (STYPE-SELECTORS {\it stype\/}) $\longrightarrow$\  {\it list of procedures\/}}}
\hfill  

\begin{inset}{}
Given a structure type {\it stype\/}, returns a list of its selector procedures.
\end{inset} 

\index{SELECTOR-ID@{\tt SELECTOR-ID}}
{\mbox {\tt (SELECTOR-ID {\it selector\/}) $\longrightarrow$\  {\it identifier\/}}}
\hfill  

\begin{inset}{}
Given a selector procedure, e.g., as returned by {\tt STYPE-SELECTOR},
returns its corresponding componentname.
\end{inset} 

\index{STYPE-HANDLER@{\tt STYPE-HANDLER}}
{\mbox {\tt (STYPE-HANDLER {\it stype\/}) $\longrightarrow$\  {\it handler\/}}}
\hfill Settable

\begin{inset}{}
Given a structure type {\it stype\/}, accesses the handler to be used
for generic operations applied to instances of the structure type.
For a newly created structure type, this handler handles
no operations, but one may set the handler to be any handler at all.
\end{inset} 

\section{Manipulating structures}


The primary means for manipulating structures is to call
their selector procedures and their setters.  For example, in the context
of the examples above, if {\tt EMPLOYEE-23} is an {\tt EMPLOYEE}-structure,
then {\tt EMPLOYEE-23}'s {\tt NAME} component may be retrieved
by evaluating
\begin{codexenv}
(EMPLOYEE-NAME EMPLOYEE-23)
\end{codexenv}
and this value may be set by evaluating
\begin{codexenv}
(SET (EMPLOYEE-NAME EMPLOYEE-23) 'FRED)
\end{codexenv}

This works because the selector procedures for {\tt EMPLOYEE-STYPE}
handle the generic operation called {\tt SETTER}.
Structures may also be manipulated using other generic operations.

\index{STRUCTURE?@{\tt STRUCTURE?}}
{\mbox {\tt (STRUCTURE? {\it object\/}) $\longrightarrow$\  {\it boolean\/}}}
\hfill Type predicate

\begin{inset}{}
Returns true if {\it object\/} is a structure.
\end{inset} 

\index{COPY-STRUCTURE@{\tt COPY-STRUCTURE}}
{\mbox {\tt (COPY-STRUCTURE {\it structure\/}) $\longrightarrow$\  {\it structure\/}}}
\hfill  

\begin{inset}{}
Makes a copy of {\it structure\/}.  The value returned is a new object
of the same structure type as {\it structure\/} whose components
are the same (in the {\tt EQ?} sense) as {\it structure\/}'s.
\end{inset} 

\index{COPY-STRUCTURE!@{\tt COPY-STRUCTURE!}}
{\mbox {\tt (COPY-STRUCTURE! {\it destination source\/}) $\longrightarrow$\  {\it structure\/}}}
\hfill  

\begin{inset}{}
Copies the components of {\it source\/} into {\it destination\/}, which
is returned.
{\it Source\/} and {\it destination\/} must be structures of the same type.
\end{inset} 
